package com.zwy.leetcode;

public class Day15Test {
    /**
     * 42. 接雨水
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int start=0;
        int count=0;
        int max=0;
        int []dp=new int[height.length];
        dp[dp.length-1]=height[height.length-1];
        max=dp[dp.length-1];
        for (int i = dp.length-2; i >=0 ; i--) {
            max=Math.max(max,height[i+1]);
            dp[i]=max;
        }
        if(height[0]>dp[0])height[0]=dp[0];
        for (int i = 1; i < height.length-1; i++) {
            if(height[i]>dp[i]){
                height[i]=dp[i];
                start++;
                continue;
            }
            else if(height[i]>height[start]&&height[i]<dp[i])start=i;
            else if(height[i]<height[start]&&height[i]<dp[i]){
                count+=height[start]-height[i];
            }

        }
        return count;
    }

    /**
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        int []res=new int[k];
        int count=0;
        int index=-1;
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if(count<k){
                res[count]=arr[i];
                if(max<arr[i]){
                    max=arr[i];
                    index=i;
                }
                count++;
            }
            else{
                if(arr[i]<max){
                    max=res[index];
                    res[index]=arr[i];
                }
            }
        }

        return res;
    }
    public static void main(String[] args) {
        int []arr={0,1,1,2,4,4,1,3,3,2};
        int k = 6;
        Day15Test test=new Day15Test();
        test.getLeastNumbers(arr,k);
    }
}
